package com.yun.algorithmproblem.leetcodenotcomplete;

import java.util.LinkedList;

/**
 * 2555. 两个线段获得的最多奖品
 * <p>
 * 在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。
 * <p>
 * 你可以同时选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。
 * <p>
 * 比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。
 * 请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。
 */
public class Leetcode2555 {

    /*
    k 对应 k+1个数
    length <= 2*(k+1),选取全部数据.
    当length>2*(k+1)时,一定选取不重复的段.

    先用计数排序将prizePositions转化成每个点上的数据 x

    先用动态数组统计?需要吗?第一重循环能顺便做吗?

    方案一:2重循环+队列? o(n^2)

    方案二:1循环计算k之和+1循环计算最大值
     */
    public int maximizeWin(int[] prizePositions, int k) {
        LinkedList<int[]> stack = new LinkedList<>();
        int total = 0;
        int curr = 0;
        for (int i = 1; i < prizePositions.length; i++) {
            if (stack.peek() == null || prizePositions[i] == stack.peek()[0]) {
                int[] pop = stack.pop();
                pop[1]++;
                stack.push(pop);
            } else {
                stack.push(new int[]{prizePositions[i], 1});
            }
        }
        if (stack.size() <= (k << 1) + 2) {

        }
        return 0;
    }
}
